package com.mc.algorithm;

//剑指offer37题
public class SumTrack {
	public static Node search(Node list1, Node list2){
		
		if(list1==null||list2==null)
			return null;
		
		Node p1 = list1;
		Node p2 = list2;
		int count1=0;
		int count2=0;
		while(p1!=null){
			p1 = p1.next;
			count1++;
		}
		while(p2!=null){
			p2 = p2.next;
			count2++;
		}
		p1 = list1;
		p2 = list2;
		int diff = Math.abs(count1-count2);
		if(count1>count2){
			for(int i=0;i<diff;i++)
				p1 = p1.next;
		}
		else{
			for(int i=0;i<diff;i++)
				p2 = p2.next;
		}
		while(p1!=p2){
			p1 = p1.next;
			p2 = p2.next;
		}
		return p1;
	}
	
	static class Node{
		int value;
		Node next;
	}
	public static void main(String[] args){
		Node[] n = new Node[4];
		for(int i=0;i<n.length;i++){
			n[i] = new Node();
			n[i].value = i;
		}
		for(int i=0;i<n.length;i++){
			if(i==n.length-1)
				n[i].next = null;
			else
				n[i].next = n[i+1];
		}
		Node m = new Node();
		m.value = 5;
		m.next = n[2];
		
		Node res = SumTrack.search(n[0], m);
		System.out.println(res.value);
	}
}

